package com.sxkiler.demo.test.threads;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;


/**
 关于CAS

 compare and swap，比较和替换技术，将预期值与当前变量的值比较(compare)，如果相等则使用新值替换(swap)当前变量，否则不作操作；

 现代CPU已广泛支持CAS指令，如果不支持，那么JVM将使用自旋锁，与互斥锁一样，两者都需先获取锁才能访问共享资源，但互斥锁会导致线程进入睡眠，而自旋锁会一直循环等待直到获取锁；

 另外，有一点需要注意的是CAS操作中的ABA问题，即将预期值与当前变量的值比较的时候，即使相等也不能保证变量没有被修改过，因为变量可能由A变成B再变回A,解决该问题，可以给变量增加一个版本号，每次修改变量时版本号自增，比较的时候，同时比较变量的值和版本号即可
 Atomic包主要提供四种原子更新方式

 原子方式更新基本类型
 原子方式更新数组
 原子方式更新引用
 原子方式更新字段

 原子方式更新基本类型

 以下三个类是以原子方式更新基本类型

 AtomicBoolean：原子更新布尔类型。
 AtomicInteger：原子更新整型。
 AtomicLong：原子更新长整型。

 */

public class LockFreeQueue {

    private AtomicReferenceArray atomicReferenceArray;
    //代表为空，没有元素
    private static final  Integer EMPTY = null;
    //头指针,尾指针
    AtomicInteger head,tail;


    public LockFreeQueue(int size){
        atomicReferenceArray = new AtomicReferenceArray(new Integer[size + 1]);
        head = new AtomicInteger(0);
        tail = new AtomicInteger(0);
    }

    /**
     * 入队
     * @param element
     * @return
     */
    public boolean add(Integer element){
        int index = (tail.get() + 1) % atomicReferenceArray.length();
        if( index == head.get() % atomicReferenceArray.length()){
            System.out.println("当前队列已满,"+ element+"无法入队!");
            return false;
        }
        while(!atomicReferenceArray.compareAndSet(index,EMPTY,element)){
            return add(element);
        }
        tail.incrementAndGet(); //移动尾指针
        System.out.println("入队成功!" + element);
        return true;
    }

    /**
     * 出队
     * @return
     */
    public Integer poll(){
        if(head.get() == tail.get()){
            System.out.println("当前队列为空");
            return null;
        }
        int index = (head.get() + 1) % atomicReferenceArray.length();
        Integer ele = (Integer) atomicReferenceArray.get(index);
        if(ele == null){ //有可能其它线程也在出队
            return poll();
        }
        while(!atomicReferenceArray.compareAndSet(index,ele,EMPTY)){
            return poll();
        }
        head.incrementAndGet();
        System.out.println("出队成功!" + ele);
        return ele;
    }

    public void print(){
        StringBuffer buffer = new StringBuffer("[");
        for(int i = 0; i < atomicReferenceArray.length() ; i++){
            if(i == head.get() || atomicReferenceArray.get(i) == null){
                continue;
            }
            buffer.append(atomicReferenceArray.get(i) + ",");
        }
        buffer.deleteCharAt(buffer.length() - 1);
        buffer.append("]");
        System.out.println("队列内容:"    +buffer.toString());

    }

}
